package com.moyoutian.leetcode;


/**
 * 108. 将有序数组转换为二叉搜索树
 * <p>
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 * <p>
 * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [1,3]
 * 输出：[3,1]
 * 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 按 严格递增 顺序排列
 */
public class Demo108 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[10];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i;
        }
        TreeNode root = sortedArrayToBST(nums);
        System.out.println();
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int avg = (nums.length) / 2;
        TreeNode root = new TreeNode(nums[avg]);
        sortedArrayToBST(nums, 0, nums.length - 1, avg, root);
        return root;
    }

    public static void sortedArrayToBST(int[] nums, int left, int right, int avg, TreeNode root) {
        if (right <= nums.length - 1 && left >= 0 && left < right) {
            if (right >= avg && avg > left) {
                int leftAvg = left + (avg - left) / 2;
                if (leftAvg != avg) {
                    root.left = new TreeNode(nums[leftAvg]);
                    sortedArrayToBST(nums, left, avg - 1, leftAvg, root.left);
                }

            }
            if (right >= avg && avg >= left) {
                int rightAvg = avg + (right - avg + 1) / 2;
                if (rightAvg != avg) {
                    root.right = new TreeNode(nums[rightAvg]);
                    sortedArrayToBST(nums, avg + 1, right, rightAvg, root.right);
                }
            }
        }
    }


    public static TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }


}
